1. Field of the Invention
The present invention relates to redundant array of independent disks (RAID) systems for generating parities for data and for recovering data using the generated parities, and also to data recovery apparatuses using Galois fields. More particularly, the invention relates to a RAID system for generating parities for data by using a Galois field multiplication table and for recovering data using the generated parities, and also to a data recovery apparatus using a Galois field.
2. Description of the Related Art
Due to the recent spread of digitization, data is becoming more and more important. Accordingly, data recovery techniques for recovering lost data from other data and parities are required. One approach to recovering data from double failure is RAID-6. In this RAID-6 scheme, a linear redundancy technique has been proposed, as disclosed in, for example, Japanese Unexamined Patent Application Publication No. 2000-259359 (FIGS. 5 and 6).
This technique is described below in the context of the configuration of the RAID-6 system shown in FIG. 8. Five data disk units (hard disk drives) 101, 102, 103, 104, and 105 and two parity disk units (hard disk drives), i.e., disk units 106 and 107, are connected to a RAID controller 110 through a bus 112 therebetween.
In the linear redundancy technique, two parities are generated from data. The first parity P is generated, as shown in FIG. 10, as a result of adding data items D0, D1, D2, D3, and D4, i.e., calculating exclusive OR (XOR), as in the known RAID-5 scheme. The first parity P is stored in the parity disk unit 106. The sign “+” represents XOR in the following description. A data item (for example, D0, D1, D2, D3, . . . ) on which a Galois field computation is performed is also described as “symbol” in the following description.
The second parity Q is generated by weighting the data items D0, D1, D2, D3, and D4 using Galois field product generators A0 through A4 (α0 through α4) respectively, and by computing XOR of the resulting values. That is, the second parity Q is generated by the following equation (1).Q=A0*D0+A1*D1+A2*D2+A3*D3+A4*D4  (1)
The second parity Q is then stored in the second parity disk unit 107.
Among the Galois field generators A0 through A4 (α0 through α4), one Galois field generator is assigned to each of the data disk units 101, 102, 103, 104, and 105. In order to recover data from a single disk failure or double disk failures, it is necessary that the Galois field generators assigned to the data disk units 101, 102, 103, 104, and 105 be different from each other. For example, if the number of data bits is 16, as shown in FIG. 10, 216 finite elements are provided as the Galois field GF (216). Additionally, four arithmetic operations can be performed on the Galois field according to a predetermined rule (XOR of Galois field generators having the same order results in 0 (e.g., α1+α1=0), and multiplication of Galois field generators results in the addition of those orders (e.g., α2×α3=α5)). The linear redundancy technique allows distribution of parities and is effective for detecting the occurrence of double disk failures and recovering data from such failures.
In the case of a single disk failure occurring in, for example, the data disk unit 102, to recover data D1, the following equation (2) is obtained by modifying equation (1).A1*D1=A0*D0+A2*D2+A3*D3+A4*D4+Q  (2)
From equation (2), by the use of the parity Q, and data other than data D1, i.e., data D0 and D2 through D4, and Galois field generators, such as A0 and A2 through A4 and (A1)−1, data D1 can be recovered according to the following equation (3).D1=(A1)−1*(A0*D1+A2*D2+A3*D3+A4*D4+Q)  (3)
Data D1 can be recovered by the use of the parity P. However, by considering the case where the reliability of the parity P is low, an algorithm for recovering data D1 using the parity Q is prepared.
In the case of double disk failures occurring in, for example, the data disk units 102 and 103, to recover data D1 and D2, the following equation (4) is obtained from equation (1).A1*D1+A2*D2=A0*D0+A3*D3+A4*D4+Q  (4)
If the right side of equation (4) is represented by F, the following equation (5) is found.A1*D1+A2*D2=F  (5)
Then, by modifying the equation for generating the parity P shown in FIG. 10, the following equation (6) is obtained.D1+D2=D0+D3+D4+P  (6)
If the right side of equation (6) is represented by G, the following equation (7) is found.D1+D2=G  (7)
By the use of equations (5) and (7), simultaneous equations for the data D1 and D2 are established and then solved. First of all, by multiplying equation (7) by A1, the following equation (8) is obtained.A1*D1+A1*D2=A1*G  (8)
By adding equations (XOR) (5) and (8), the following equation (9) is determined.(A1+A2)*D2=F+A1*G  (9)
By modifying equation (9), the following equation (10) for the data D2 is obtained.D2=(A1+A2)−1*(F+A1*G)  (10)
By modifying equation (7), the following equation (11) for the data D1 is obtained.D1=D2+G  (11)
By substituting F in equations (4) and (5) and G in equations (6) and (7) into the right side of equation (10), the following equation (12) for recovering the data D2 is obtained.
                              D          ⁢                                          ⁢          2                =                                            (                                                A                  ⁢                                                                          ⁢                  1                                +                                  A                  ⁢                                                                          ⁢                  2                                            )                                      -              1                                *                      (                                          A                ⁢                                                                  ⁢                0                *                D                ⁢                                                                  ⁢                0                            +                              A                ⁢                                                                  ⁢                3                *                D                ⁢                                                                  ⁢                3                            +                              A                ⁢                                                                  ⁢                4                *                D                ⁢                                                                  ⁢                4                            +              Q              +                              A                ⁢                                                                  ⁢                1                *                D                ⁢                                                                  ⁢                0                            +                              A                ⁢                                                                  ⁢                1                *                D                ⁢                                                                  ⁢                3                            +                              A                ⁢                                                                  ⁢                1                *                D                ⁢                                                                  ⁢                4                            +                              A                ⁢                                                                  ⁢                1                *                P                                      )                                              (        12        )            
Similarly, by substituting G in equations (6) and (7) into the right side of equation (11), the following equation (13) for recovering the data D1 is obtained.D1=D0+D2+D3+D4+P  (13).
In generating parities and recovering data by utilizing a Galois field, two variables, such as data D and Galois field generator A, are necessary for executing Galois field product computation. Accordingly, a longer processing time is required for generating parities than that for XOR computation of the RAID-5 scheme, i.e., computation of the ordinary parity P, thereby reducing the performance.
To simplify the Galois field product computation, the following technique, disclosed in, for example, Japanese Unexamined Patent Application Publication No. 2000-259359 (FIGS. 5 and 6), has been proposed. In this technique, a Galois field product computation table 120 storing multiplication results of data D and Galois field generator A is generated, as shown in FIG. 9, and by referring to the Galois field product computation table 120, product computation results for individual data items and Galois field generators are obtained.
It is now assumed that, in a RAID system, n data and two parities are used and that one symbol has 16 bits and the Galois field is GF(216). In this case, the Galois field generators A required for weighting the data disks are represented by αi1, αi2, αi3, . . . , αin (ijε{0, 1, . . . , 65534}).
When using the above-described Galois field generators A, the weighting values used for recovering data from single-disk failures are α−i1, α−i2, α−i3, . . . , α−in, as expressed by equation (3). The weighting values used for double disk failures can be determined by the following equation (14) from equation (12).(αij+αik)−1(j=1, . . . ,n−1, k=j+1, . . . ,n)  (14)
Accordingly, if the weighting values are randomly selected, as in the related art, weighting values used for single disk failures and weighting values used for double disk failures are not overlapped, and thus, the number of Galois field generators required is equal to the sum of the number n of data disk units, the number n of possible single disk failures, and the number n(n−1)/2 of possible double disk failures.
The number of possible values that can be taken as one symbol (16-bit) D is 216=65536. Accordingly, if the Galois field product computation table 120 storing the Galois field generators used for weighting and possible symbol values for one symbol is generated, as shown in FIG. 9, (n+n+n(n−1)/2)×65536 data elements are required. For example, if n=14, 119×65536 data elements are required. This significantly increases the data amount of the tables, i.e., the space of the memory, which makes the RAID system and the data recovery apparatus expensive.